package Basic;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

import org.rtscup.core.Resource;

import Game.Blackboard;

/**
 * 
 * @author egg Classe que representa a visao em Tiles dos agentes
 * 
 */
public class Tiles {

	private int width; // Largura do mapa
	private int height; // Altura do mapa
	private int noTilesW; // Numero de tiles onde a largura sera subdividida
	private int noTilesH; // Numero de tiles onde a altura sera subdividida

	// As constantes que representam o tipo do obstaculo
	private final static int FREE_TILE = 0;
	public final static int SIMPLE_OBSTACLE = 1;
	public final static int DYNAMIC_OBSTACLE = 2;

	private int[] obstacles; // Vetor de inteiros que contem o tipo de obstaculo

	private int totalTiles;
	private static Comparator<Long> comparator = new Comparator<Long>() {

		@Override
		public int compare(Long o1, Long o2) {
			return (int) ((o1 & 0xFFFFFFFF) - (o2 & 0xFFFFFFFF));
		}
	};

	// para cada tile.

	/**
	 * 
	 * Construtor
	 * 
	 * @param width
	 * @param height
	 * @param noTilesW
	 * @param noTilesH
	 * @param obstacles
	 */
	public Tiles(int width, int height, int noTilesW, int noTilesH, StaticObstacle[] obstacles, Blackboard blackboard) {
		this.width = width;
		this.height = height;
		this.noTilesW = noTilesW;
		this.noTilesH = noTilesH;
		this.obstacles = new int[this.noTilesW * this.noTilesH];

		for (int i = 0; i < obstacles.length; i++) {
			this.addObstacle(obstacles[i], SIMPLE_OBSTACLE);
		}

		this.totalTiles = this.noTilesW * this.noTilesH;
	}

	/**
	 * Dado um ponto p, ele retorna o ponto central do tile no qual aquele ponto
	 * esta contido
	 * 
	 * @param p
	 * @return O ponto central do tile no qual p esta contido
	 */
	public Point getCentral(Point p) {
		return this.getCentral(this.getTile(p.x, p.y));
	}

	/**
	 * Retorna o ponto central do tile passado como parametro
	 * 
	 * @param tile
	 * @return O ponto central do tile
	 */
	public Point getCentral(int tile) {
		int w = tile % this.noTilesW;
		int h = (tile - w) / this.noTilesW;
		double wm = (double) w + 0.5;
		double hm = (double) h + 0.5;
		Point ret = new Point((int) (wm * (this.width / this.noTilesW)), (int) (hm * (this.height / this.noTilesH)));
		return ret;
	}

	/**
	 * Retorna o tile no qual o ponto p esta contido
	 * 
	 * @param p
	 * @return - O tile no qual p esta contido
	 */
	public int getTile(int pointX, int pointY) {
		int x = 0;
		int y = 0;
		if (pointX >= this.width)
			x = this.width - 1;
		else
			x = pointX;
		if (pointY >= this.height)
			y = this.height - 1;
		else
			y = pointY;
		int w = x / (this.width / this.noTilesW);
		int h = y / (this.height / this.noTilesH);
		return ((w * 1) + (h * this.noTilesW));
	}

	/**
	 * Retorna um vetor com todos os tiles vizinhos do tile passado como
	 * parametro
	 * 
	 * @param tile
	 * @return Todos os vizinhos possiveis ou nao
	 */
	public List<Integer> get4Neighbors(int tile) {

		List<Integer> ret = new ArrayList<Integer>();

		// Vizinhos de cima
		if (tile / this.noTilesW >= 1) {
			ret.add(tile - (this.noTilesW)); // Vizinho exatamente acima
		}

		// Vizinhos do lado
		if (tile % this.noTilesW != 0)
			ret.add(tile - 1); // Vizinho da esquerda
		if ((tile + 1) % this.noTilesW != 0)
			ret.add(tile + 1); // Vizinho da direita

		// Vizinhos de baixo
		if (tile / this.noTilesW < (this.noTilesH - 1)) {
			ret.add(tile + (this.noTilesW)); // Vizinho exatamente abaixo
		}

		return ret;
	}

	private List<Integer> get8Neighbors(int tile) {
		List<Integer> ret = new ArrayList<Integer>();

		boolean hasUp = tile / this.noTilesW >= 1;
		boolean hasDown = tile / this.noTilesW < (this.noTilesH - 1);
		boolean hasLeft = tile % this.noTilesW != 0;
		boolean hasRight = (tile + 1) % this.noTilesW != 0;

		if (hasUp) {
			ret.add(tile - this.noTilesW);
		}
		if (hasDown) {
			ret.add(tile + this.noTilesW);
		}
		if (hasLeft) {
			ret.add(tile - 1);
		}
		if (hasRight) {
			ret.add(tile + 1);
		}
		if (hasUp && hasLeft) {
			ret.add(tile - this.noTilesW - 1);
		}
		if (hasUp && hasRight) {
			ret.add(tile - this.noTilesW + 1);
		}
		if (hasDown && hasLeft) {
			ret.add(tile + this.noTilesW - 1);
		}
		if (hasDown && hasRight) {
			ret.add(tile + this.noTilesW + 1);
		}

		return ret;
	}

	/**
	 * Retorna um vetor com todos os tiles vizinhos possiveis do tile passado
	 * como parametro
	 * 
	 * @param tile
	 * @return Todos os vizinhos possiveis (que nao sao obstaculo, nem sao fora
	 *         do mapa) do tile
	 */
	public ArrayList<Integer> getNeighborsTiles(int tile) {

		ArrayList<Integer> ret = new ArrayList<Integer>();

		// Vizinhos de cima
		if (tile / this.noTilesW >= 1) {
			if (this.obstacles[tile - (this.noTilesW)] <= Tiles.FREE_TILE)
				ret.add(tile - (this.noTilesW));
		}

		// Vizinhos do lado
		if (tile % this.noTilesW != 0 && this.obstacles[tile - 1] <= Tiles.FREE_TILE)
			ret.add(tile - 1);
		if ((tile + 1) % this.noTilesW != 0 && this.obstacles[tile + 1] <= Tiles.FREE_TILE)
			ret.add(tile + 1);

		// Vizinhos de cima
		if (tile / this.noTilesW < (this.noTilesH - 1)) {
			if (this.obstacles[tile + (this.noTilesW)] <= Tiles.FREE_TILE)
				ret.add(tile + (this.noTilesW));
		}

		return ret;
	}

	/**
	 * Chama o A* para dois pontos
	 * 
	 * @param start
	 *            (inicio do A*)
	 * @param goal
	 *            (objetivo do A*)
	 * @return Um vetor de pontos com o caminho INVERSO entre start e goal -
	 *         Para calcular o caminho correto basta mudar a ordem dos
	 *         parametros. Nao retorna (no caminho) o start e o goal.
	 */
	public ArrayList<Point> aStar(int xStart, int yStart, int xGoal, int yGoal) {
		return this.aStar(this.getTile(xStart, yStart), this.getTile(xGoal, yGoal));
	}

	/**
	 * Calcula o A* para dois tiles
	 * 
	 * @param start
	 *            (inicio do A*)
	 * @param goal
	 *            (objetivo do A*)
	 * @return Um vetor de pontos com o caminho INVERSO entre start e goal -
	 *         Para calcular o caminho correto basta mudar a ordem dos
	 *         parametros. Nao retorna (no caminho) o start e o goal.
	 */
	public ArrayList<Point> aStar(int start, int goal) {

		ArrayList<Integer> closedSet = new ArrayList<Integer>();
		// ArrayList<Integer> openSet = new ArrayList<Integer>();
		// BinaryHeap openSet = new BinaryHeap();
		PriorityQueue<Long> openSet = new PriorityQueue<Long>(100, comparator);

		int[] g = new int[totalTiles];
		int[] h = new int[totalTiles];
		int[] f = new int[totalTiles];
		boolean[] isInOpenSet = new boolean[totalTiles];
		boolean[] isInClosedSet = new boolean[totalTiles];
		int[] cameFrom = new int[totalTiles];
		for (int i = 0; i < cameFrom.length; i++) {
			cameFrom[i] = -1;
		}

		g[start] = 0;
		h[start] = this.euclidean(this.getCentral(start), this.getCentral(goal));
		f[start] = h[start];
		isInOpenSet[start] = true;
		openSet.add(newTuple(start, f[start]));

		while (!openSet.isEmpty()) {

			// int x = openSet.remove().tile;
			int x = (int) (openSet.remove() >> 32);
			isInOpenSet[x] = false;

			closedSet.add(x);
			isInClosedSet[x] = true;

			ArrayList<Integer> neighbors = this.getNeighborsTiles(x);
			for (int i = 0; i < neighbors.size(); i++) {

				int y = neighbors.get(i);

				if (!isInClosedSet[y]) {

					int tentativeG = g[x] + (this.width / this.noTilesW);

					if (!isInOpenSet[y]) {
						cameFrom[y] = x;
						g[y] = tentativeG;
						h[y] = this.euclidean(this.getCentral(y), this.getCentral(goal));
						f[y] = g[y] + h[y];
						openSet.add(newTuple(y, f[y]));
						isInOpenSet[y] = true;
					} else if (tentativeG < g[y]) {
						cameFrom[y] = x;
						g[y] = tentativeG;
						h[y] = this.euclidean(this.getCentral(y), this.getCentral(goal));
						f[y] = g[y] + h[y];
					}
				}
			}
		}

		ArrayList<Point> ret = new ArrayList<Point>();
		int iter = goal;
		boolean noPath = false;
		while (cameFrom[iter] != start) {
			if (cameFrom[iter] == -1) {
				noPath = true;
				break;
			}
			iter = cameFrom[iter];
			ret.add(this.getCentral(iter));
		}

		if (noPath) {
			// System.out.println("There is no path!");
			return new ArrayList<Point>();
		} else {
			return ret;
		}
	}

	private Long newTuple(int start, int i) {
		long result = ((long) start) << 32;
		result |= i & 0xFFFFFFFF;
		return result;
	}

	public void removeObstacle(StaticObstacle so, int type) {
		int tile1 = this.getTile(so.x - (so.width / 2), so.y - (so.height / 2));
		int tile2 = this.getTile(so.x - 1 + (so.width / 2), so.y - (so.height / 2));
		int tile3 = this.getTile(so.x - (so.width / 2), (so.y - 1) + (so.height / 2));
		int rangeW = tile2 - tile1 + 1;
		int rangeH = ((tile3 - tile1) / this.noTilesW) + 1;

		for (int m = 0; m < rangeH; m++) {
			for (int n = 0; n < rangeW; n++) {
				int tile = n + (m * this.noTilesW) + tile1;
				this.obstacles[tile] = this.obstacles[tile] - type;
			}
		}
	}

	/**
	 * Adiciona um obstaculo comum - Obstacle, Resource e Building
	 * 
	 * @param so
	 *            - Obstaculo a ser adicionado
	 */
	public void addObstacle(StaticObstacle so, int type) {
		int tile1 = this.getTile(so.x - (so.width / 2), so.y - (so.height / 2));
		int tile2 = this.getTile((so.x - 1) + (so.width / 2), so.y - (so.height / 2));
		int tile3 = this.getTile(so.x - (so.width / 2), (so.y - 1) + (so.height / 2));
		int rangeW = tile2 - tile1 + 1;
		int rangeH = ((tile3 - tile1) / this.noTilesW) + 1;

		for (int m = 0; m < rangeH; m++) {
			for (int n = 0; n < rangeW; n++) {
				int tile = n + (m * this.noTilesW) + tile1;
				this.obstacles[tile] = this.obstacles[tile] + type;
			}
		}
	}

	/**
	 * Calcula a distancia euclideana entre dois pontos
	 * 
	 * @param p1
	 * @param p2
	 * @return A distancia euclideana entre p1 e p2
	 */
	public int euclidean(Point p1, Point p2) {
		return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
	}

	public List<Integer> getAvailableNeighborTiles(int posX, int posY) {
		List<Integer> ret;

		int tile = getTile(posX, posY);
		ret = new ArrayList<Integer>();
		List<Integer> neighbors = get8Neighbors(tile);

		for (Integer neighbor : neighbors) {
			if (isAvailable(neighbor)) {
				ret.add(neighbor);
			}
		}

		return ret;
	}

	public boolean isAvailable(int tile) {
		boolean ret;

		ret = obstacles[tile] == 0;

		return ret;
	}

	public List<StaticObstacle> getMineAsObstacles(Resource res) {
		List<StaticObstacle> ret;

		ret = new ArrayList<StaticObstacle>();

		int tile = getTile(res.getX(), res.getY());
		int w = res.getWidth();
		int h = res.getHeight();

		boolean hasUp = tile - this.noTilesW >= 0;
		boolean has2Up = tile - 2 * this.noTilesW >= 0;

		boolean hasDown = tile + this.noTilesW < this.totalTiles;
		boolean has2Down = tile + 2 * this.noTilesW < this.totalTiles;

		boolean hasLeft = tile % this.noTilesW != 0;
		boolean has2Left = hasLeft && (tile - 1) % this.noTilesW != 0;

		boolean hasRight = (tile + 1) % this.noTilesW != 0;
		boolean has2Right = hasRight && (tile + 2) % this.noTilesW != 0;

		Point p;
		if (hasUp) {
			p = this.getCentral(tile - this.noTilesW);
			ret.add(new StaticObstacle(p.x, p.y, w, h));

			if (has2Up) {
				p = this.getCentral(tile - 2 * this.noTilesW);
				ret.add(new StaticObstacle(p.x, p.y, w, h));
			}
		}

		if (hasDown) {
			p = this.getCentral(tile + this.noTilesW);
			ret.add(new StaticObstacle(p.x, p.y, w, h));

			if (has2Down) {
				p = this.getCentral(tile + 2 * this.noTilesW);
				ret.add(new StaticObstacle(p.x, p.y, w, h));
			}
		}

		if (hasLeft) {
			p = getCentral(tile - 1);
			ret.add(new StaticObstacle(p.x, p.y, w, h));

			if (has2Left) {
				p = this.getCentral(tile - 2);
				ret.add(new StaticObstacle(p.x, p.y, w, h));
			}
		}

		if (hasRight) {
			p = getCentral(tile + 1);
			ret.add(new StaticObstacle(p.x, p.y, w, h));

			if (has2Right) {
				p = this.getCentral(tile + 2);
				ret.add(new StaticObstacle(p.x, p.y, w, h));
			}
		}

		if (hasUp && hasLeft) {
			p = getCentral(tile - this.noTilesW - 1);
			ret.add(new StaticObstacle(p.x, p.y, w, h));
		}

		if (hasUp && hasRight) {
			p = getCentral(tile - this.noTilesW + 1);
			ret.add(new StaticObstacle(p.x, p.y, w, h));
		}

		if (hasDown && hasLeft) {
			p = getCentral(tile + this.noTilesW - 1);
			ret.add(new StaticObstacle(p.x, p.y, w, h));
		}

		if (hasDown && hasRight) {
			p = getCentral(tile + this.noTilesW + 1);
			ret.add(new StaticObstacle(p.x, p.y, w, h));
		}

		p = getCentral(tile);
		ret.add(new StaticObstacle(p.x, p.y, w, h));

		return ret;
	}

	public static void main(String[] args) {

		/*
		 * StaticObstacle so1 = new StaticObstacle(600, 400, 400, 200);
		 * StaticObstacle so2 = new StaticObstacle(1150, 500, 300, 400);
		 * StaticObstacle so3 = new StaticObstacle(300, 750, 600, 100);
		 * StaticObstacle so4 = new StaticObstacle(600, 850, 600, 100);
		 * StaticObstacle[] socol = { so1, so2, so3, so4 };
		 * 
		 * Tiles tiles = new Tiles(1700, 1000, 17, 10, socol, blackboard);
		 * 
		 * ArrayList<Point> path = tiles.aStar(3, 155); for (int i = 0; i <
		 * path.size(); i++) {
		 * System.out.println(tiles.getTile(path.get(i).getX(),
		 * path.get(i).getY())); }
		 */

	}

}
